package dp;

/**
 * 509. 斐波那契数
 *
 * 斐波那契数列
 * （从0开始，第0项为0，第1项是1）
 * 0 1 1 2 3 5 8 13 21 34 55 89
 */
public class Solution {
    public static void main(String[] args) {
        /**
         * 递归会重复算很多值，动态规划是正向的根据签名的值。所以推荐使用动态规划
         */
        System.out.println(new Solution().Fibonacci1(6));
    }
    /**
     * 动态规划
     */
    public int Fibonacci1(int n){
        if (n==0){
            return 0;
        }else if (n==1){
            return 1;
        }else {
            int[] dp=new int[n+1];
            dp[0]=0;
            dp[1]=1;
            for (int i = 2; i < n + 1; i++) {
                dp[i]=dp[i-1]+dp[i-2];
            }
            return dp[n];
        }
    }

    /**
     * 递归实现
     */
    public int Fibonacci2(int n){
        if (n==0){
            return 0;
        }else if (n==1){
            return 1;
        }else {
            return Fibonacci2(n-1)+Fibonacci2(n-2);
        }
    }

}
